package com.hy;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:寻找两个正序数组的中位数
 * author: Mr.Du
 * Date: 2023/6/2
 * Time: 19:20
 */
public class FindMedianSortedArrays {
    
    
    public static void main(String[] args) {
        int[] nums1 = {1, 2};
        int[] nums2 = {3, 4, 5};
        double res = findMedianSortedArrays(nums1, nums2);
        System.out.println(res);
    }
    
    /**
     题解并没有很好的利用数组的有序性， 我们换一个思路更好理解吧，先看求一个
     有序数组的中位 数，使用双指针方法 算法： 1：求一个数组的中位数，使用双指
     针方法，left++, right--， 当left, right相遇时， 中位数就等于
     (num[left]+num[right])/2; 推导出结论：当两个指针相遇时，left, right指针
     分别都走了(num.size() + 1)/2步，中位数等于(num[left]+num[right])/2, 不论数组
     长度奇偶该结论都成立;
     现在是要让我们求两个数组的中位数，可以把两个数组合成的大的数组想象成一个逻辑数组，
     分配两个指针left_num, right_num，两指针分别走
     step = (num1.size() + num2.size() + 1) / 2步，
     中位数就是(left_num+right_num)/2; 需要额外考虑的就是left_num，right_num指针的
     增减是分别在两个数组中完成，和一些边界问题就可以了；
     这个思路可以扩展到求N个数组的中位数。
     */
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int l1 = 0;
        int r1 = nums1.length - 1;
        int l2 = 0;
        int r2 = nums2.length - 1;
        
        double left_num = 0;
        double right_num = 0;
        int step = ((nums1.length + nums2.length) + 1)/2;
        while(step > 0) {
            if (r1 - l1 < 0) {
                left_num = nums2[l2++];
                right_num = nums2[r2--];
            } else if (r2 - l2 < 0) {
                left_num = nums1[l1++];
                right_num = nums1[r1--];
            } else {
                left_num = nums1[l1] <= nums2[l2]?  nums1[l1++] : nums2[l2++];
                right_num = nums1[r1] >= nums2[r2]? nums1[r1--] : nums2[r2--];
            }
            step--;
        }
        double ans = (left_num + right_num) / 2;
        return ans;
    }
}
